package com.some;

public class Dijkstra_test_3 {
    public static final int M = 10000; // 代表正无穷

    public static void main(String[] args) {
        // 二维数组每一行分别是 A、B、C、D、E 各点到其余点的距离,
        // A -> A 距离为0, 常量M 为正无穷
        int[][] weight1 = {
                {0, 4, M, 2, M},
                {4, 0, 4, 1, M},
                {M, 4, 0, 1, 3},
                {2, 1, 1, 0, 7},
                {M, M, 3, 7, 0}
        };

        int start = 0;

        int[] shortPath = dijkstra(weight1, start);

        for (int i = 0; i < shortPath.length; i++)
            System.out.println("从" + start + "出发到" + i + "的最短距离为：" + shortPath[i]);
    }

    public static int[] dijkstra(int[][] weight, int start) {
        int n = weight.length;
        int[] shortPath = new int[n];
        String[] path = new String[n];
        boolean[] visit = new boolean[n];

        for (int i = 0; i < n; i++) {
            path[i] = start + "-->" + i;
        }

        shortPath[start] = 0;
        visit[start] = true;

        for (int count = 1; count < n; count++) {
            int k = -1;
            int minDis = Integer.MAX_VALUE;
            for (int i = 0; i < n; i++) {
                if (!visit[i] && weight[start][i] < minDis) {
                    minDis = weight[start][i];
                    k = i;
                }
            }
            shortPath[k] = minDis;
            visit[k] = true;

            for (int i = 0; i < n; i++) {
                if (!visit[i] && shortPath[k] + weight[k][i] < weight[start][i]) {
                    weight[start][i] = shortPath[k] + weight[k][i];
                    path[k] += "-->" + i;
                }
            }
        }
        for (int i = 0; i < n; i++) {
            System.out.println("从" + start + "出发到" + i + "的最短路径为：" + path[i]);
        }
        System.out.println("=====================================");
        return shortPath;
    }
}
